"""
矩阵链乘问题

这个问题比较经典，直接写方程求解吧。
有n个矩阵依次相乘，求最小的乘法操作次数。已知两个矩阵相乘的乘法次数和它们的维数有关
（mns)。

输入：

    p=矩阵链的维数，n+1的数组。第i个矩阵的维数为p[i-1]xp[i]

状态转移方程：

    dp[i,j]=max{dp[i,k]+dp[k+1,j]+p[i-1]*p[k]*p[j]} for k=i to j-1


解释：i，j表示从下标i到下标j的矩阵链。dp表示相应的最优解。k表示从第k个矩阵后面切开。
因为j后面没有矩阵了，所以k不能取j。切开之后，变成两个子问题，分别求出最优解，得到两个
矩阵，维数分别是 p[i-1]xp[k] p[k]xp[j]，它们相乘的代价就是 p[i-1]*p[k]*p[j]。

边界条件：

    dp[i,j]=0, i=j

解释：表示只有一个矩阵，显然不需要相乘。

"""

P = [30, 35, 15, 5, 10, 20]
N = 5


def DP_Recur(i, j, mem, solution):
    if (i, j) in mem:
        return mem[i, j]
    val = 99999
    pos = None
    if i == j:
        val = 0
        pos = 0
    else:
        for k in range(i, j):
            temp = (
                DP_Recur(i, k, mem, solution)
                + DP_Recur(k + 1, j, mem, solution)
                + P[i - 1] * P[k] * P[j]
            )
            if temp < val:
                val = temp
                pos = k

    mem[i, j] = val
    solution[i, j] = pos
    return val


def DP_Iter():
    dp = {}
    solution = {}
    # i=j
    for i in range(1, N + 1):
        dp[i, i] = 0

    # 注意：不是打表，而是枚举所有连续的子区间。
    for r in range(2, N + 1):
        # 令j=n，
        for i in range(1, N - r + 2):
            j = r + i - 1
            val = 99999
            pos = None
            for k in range(i, j):
                print(i, j, k)
                temp = dp[i, k] + dp[k + 1, j] + P[i - 1] * P[k] * P[j]

                if temp < val:
                    val = temp
                    pos = k
            dp[i, j] = val
            solution[i, j] = pos

    val = dp[1, N]
    print("val", val)
    print("dp", dp)
    print("solution", solution)


def DP_Recur_Solve():
    mem = {}
    solution = {}
    val = DP_Recur(1, N, mem=mem, solution=solution)
    print("val", val)
    print("dp", mem)
    print("solution", solution)


DP_Iter()
